/**
 * 暴力解法 （会超时）
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
export var findKthNumber = function (m, n, k) {
  const nums = []
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      nums.push(i * j)
    }
  }
  nums.sort((a, b) => a - b)
  return nums[k - 1]
}

/**
 * 二分查找法
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
export var findKthNumber2 = function (m, n, k) {
  let [l, r] = [1, m * n]
  while (l < r) {
    const mid = l + Math.floor((r - l) / 2)
    let count = 0
    // 计算每行少于 mid 的个数
    for (let i = 1; i <= m; i++) {
      // 求出最大一个少于mid的数在第几列，即该行有多少个。 j = mid / i
      count += Math.min(Math.floor(mid / i), n)
    }
    if (count < k) {
      l = mid + 1
    } else {
      r = mid
    }
  }
  return r
}
